package _11_整理题目._2_二叉树_递归_dfs_bfs._遍历;


import org.junit.Test;
import util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
 * 例如：
 * 给定的二叉树是{3,  9,20,  #,#,15,7}
 * 该二叉树层序遍历的结果是 ArrayList<ArrayList<Integer>>
 * 
 * bfs
 * 记住层序遍历的核心：使用 队列 储存所有节点，先默认加个 root ，while(!queue.isEmpty())
 * 如果要分层存储节点，可以先获得 queue.size(), 在 fori 遍历
 * 
 */
public class _012_求二叉树的层序遍历 {
    
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        if (root == null) return new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
    
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int n = queue.size();
            ArrayList<Integer> temp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(temp);
        }
        return result;
    }
    
    @Test
    public void main() {
        Integer[] input = new Integer[]{1, 2, 3, 4, 5, 6, 7};
        TreeNode root = TreeNode.getTreeFromArray(input);
        ArrayList<ArrayList<Integer>> result = levelOrder(root);
        result.forEach(list -> System.out.println(list));
    }
}
